package cn.ihna.demo.algorithm.basic;

import cn.ihna.demo.algorithm.util.ArrayUtil;

import java.util.LinkedList;

/**
 * 最长公共子序列问题
 *
 * @author xianyingda@gmail.com
 * @serial
 * @since 2020-08-28 14:25
 */
@SuppressWarnings({"Duplicates"})
public class LCS2 {

    /**
     * 状态：arr[i][j] = s1.subString(0,i) 和 s2.subString(0,j) 的公共子序列char的个数
     * 状态转移方程：
     * if(s1(i-1)==s2(i-1)){
     *     arr[i][j] = arr[i-1][j-1] + 1
     * }else{
     *     arr[i][j] = Math.max(arr[i-1][j], arr[i][j-1]);
     * }
     */

    private static final String s1 = "123456";
    private static final String s2 = "f345a67";

    public static void main(String[] args) {
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        int l1 = c1.length;
        int l2 = c2.length;
        int[][] arr = new int[l1 + 1][l2 + 1];
        for (int i = 1; i <= l1; i++) {
            for (int j = 1; j <= l2; j++) {
                if (c1[i - 1] == c2[j - 1]) {
                    // 如果match 值为左上角+1
                    arr[i][j] = arr[i - 1][j - 1] + 1;
                } else {
                    // 否则取左边和上边的最大值
                    arr[i][j] = Math.max(arr[i - 1][j], arr[i][j - 1]);
                }
            }
        }
        ArrayUtil.printArr(arr);
        // 矩阵中的数字代表了字符串的这个位置（包含）之前的字符串最长的公共子序列的元素的个数
        LinkedList<String> list = new LinkedList<>();
        int i = l1;
        int j = l2;
        while (i > 0 && j > 0) {
            // 从右下角开始反推 当前位置的值是从何而来的
            if (c1[i - 1] == c2[j - 1]) {
                // 当前的值是左上角自增得来的，当前节点是一个match的节点
                list.addFirst(String.valueOf(c1[i - 1]));
                // 坐标移动到左上方节点
                i = i - 1;
                j = j - 1;
            } else {
                // 当前节点不是一个match的节点，值是继承来的。找到上级。
                if (arr[i][j] > arr[i - 1][j]) {
                    // 如果当前节点比其中一个大，那么就认为不是从这个节点来的，移动到另一个节点
                    j = j - 1;
                } else {
                    // 反之亦然
                    i = i - 1;
                }

            }
        }
        System.out.println(String.join("", list));
    }

}
